package binary_tree.leetcode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author Stark
 * @Date 2022/2/22 17:22
 */
public class Num662_WidthOfTree {
    public int widthOfBinaryTree(TreeNode root) {
        if(root == null){
            return 0;
        }
        Deque<TreeNodeWithNum> queue = new LinkedList<>();
        //将二叉树的根节点入队
        queue.add(new TreeNodeWithNum(root,1));
        //二叉树的最大宽度
        int maxWidth = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            int left = 0;
            int right = 0;
            //每层的宽度
            int maxLevelWidth = 0;
            for (int i = 0; i < size; i++) {
                TreeNodeWithNum nodeWithNum = queue.poll();
                //取这层最左和最右的结点的编号
                if(i == 0){
                    left = nodeWithNum.num;
                }
                if(i == size - 1){
                    right = nodeWithNum.num;
                }
                //按照以根节点编号为1的规则给每个结点进行编号
                if(nodeWithNum.node.left != null){
                    queue.add(new TreeNodeWithNum(nodeWithNum.node.left,nodeWithNum.num * 2 ));
                }
                if(nodeWithNum.node.right != null){
                    queue.add(new TreeNodeWithNum(nodeWithNum.node.right,nodeWithNum.num * 2 + 1));
                }
            }
            //两个编号相减就是这层的最大宽度
            maxLevelWidth = right - left + 1;
            //比较每层的宽度,选出最大的就是该二叉树的宽度
            maxWidth = Math.max(maxWidth,maxLevelWidth);
        }
        return maxWidth;
    }
}
//给二叉树结点带上完全二叉树的编号
class TreeNodeWithNum{
    TreeNode node;
    int num;
    public TreeNodeWithNum(TreeNode node,int num){
        this.node = node;
        this.num = num;
    }
}